package edu.bupt.c1array;

import java.util.Arrays;

public class T10NextPermutation {
    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (nums.length<2){
            return;
        }

        //找到第一个逆序位置，或者为-1；
        int i;
        for (i=nums.length-2; i>=0;i--){
            if (nums[i] < nums[i+1]){
                break;
            }
        }

        //若为-1则直接全排序
        if (i==-1 && nums[0]>=nums[1]){
            Arrays.sort(nums,0,nums.length);
            return;
        }

        // 若有逆序则交换之后都排序
        for (int j=nums.length-1;j>0;j--){
            if (nums[j] > nums[i]){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                break;
            }
        }

        Arrays.sort(nums,i+1,nums.length);
    }
}
